package first.niuke.simple;

/**
 * @ClassName NC102
 * @description:
 * @author: 荣燊
 * @create: 2021-04-11 20:04
 **/
public class NC102 {
    // 最近公共祖先
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        TreeNode res = ancestor(root, o1, o2);
        return res.val;
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }

    public TreeNode ancestor (TreeNode root, int o1, int o2) {
        if (root == null) {
            return null;
        }
        if (root.val == o1 || root.val == o2) {
            return root;
        }
        TreeNode left = ancestor(root.left, o1, o2);
        TreeNode right = ancestor(root.right, o1, o2);
        if (left == null && right == null) {
            return null;
        }
        if (left != null && right != null) {
            return root;
        }
        return (left==null) ? right : left;
    }
}
